The invention relates to digital communications and, more particularly, to systems and methods for synchronizing transmission of data over multiple data paths.
In many electronic systems, large amounts of data are often transferred between components in parallel or serial format. Some components across which the data are to be transferred, for example, packet switching devices, can be extremely complex. Oftentimes, because of limitations such as pin count limits, such devices can be more efficiently implemented as multiple relatively small devices that operate in parallel, rather than as a single large device. Consequently, to accommodate this implementation, packets of data can be split into multiple portions, each of which is transferred along a separate parallel processing path to one of the devices. At the output of the devices, the portions of the data packets are reassembled or grouped into the original data packet for further processing.
There are many sources of error in reassembling or grouping the data packet portions into the original data packet. For example, in many systems, it is desirable and/or required that the individual data paths operate a synchronously with respect to each other and independently of each other and also that the grouping device be located a substantial distance from the individual data paths. These factors can result in a system implementation in which there is no real-time communication between the individual processing paths and the grouping device. With no inherent time relationship between portions of the data packets arriving at the grouping device that would identify the portions as belonging together in the same data packet, data packets may be formed by grouping portions that do not belong together. Other factors may also contribute to the possibility of grouping unrelated portions of data packets. For example, errors such as parity errors in one or more of the individual paths, which can be caused by such factors as noise, may result in the loss of a portion of a packet. At the grouping device, it is important to discover such errors to prevent the grouping device from inadvertently replacing the lost portion with a portion of another packet and then incorrectly reassembling the packet.
The present invention is directed to an apparatus and method for transferring data from a source to a destination which overcomes the drawbacks of the prior art such that portions of data packets formed by splitting a data packet can be reassembled into the data packet such that the number of incorrect data packets forwarded by the system is reduced or minimized. The source device is adapted to receive a plurality of packets of data for transfer to a destination device. For each packet of data to be transferred, the packet of data is split into multiple portions. A first synchronization code is associated with a first portion of the data for each packet, and a second synchronization code is associated with a second portion of the data for each packet. Along a first processing path, a first processor analyzes the first portion of data and the associated first synchronization code for each packet of data to identify a first state associated with the first portion of data for each packet. In one embodiment, a state machine of the first processor and processing path defines the state. For each packet of data, the first portion of data, its associated first synchronization code and the associated first state are stored in a first storage device. A second processor in a second processing path analyzes the second portion of data and the associated second synchronization code for each packet of data to identify a second state associated with the second portion of data for each packet. In one embodiment, this second processor includes a state machine which generates the state from the portion of the packet of data and its associated synchronization code. For each packet of data, the second portion of data, its associated second synchronization code and the associated second state are stored in a second storage device. Next, a third processor, which performs the grouping function, reads from the first storage device one of the first portions of data, its associated first synchronization code, and its associated first state and also reads from the second storage device one of the second portions of data, its associated second synchronization code, and its associated second state. The third grouping processor can analyze the first and second states and the first and second synchronization codes associated with the first and second portions of data, respectively, to determine whether the packet portions were generated from the same packet of data. If they were generated from the same packet of data, then the portions are combined to regenerate the original packet of data.
In one embodiment, if the first and second portions of data were not generated from the same packet of data, then a recovery operation is performed to recover synchronization of the portions of data such that the system can resume correctly grouping packet portions together and forwarding complete packets for further processing. This recovery operation can comprise discarding at least one portion of data. That is, in one embodiment, the system can read packet portions from the individual storage devices and, if it is determined that the portions do not belong together, at least one of them can be discarded. The discarding of packet portions can continue until synchronization is resumed. In one embodiment, where synchronization codes on one of the processing paths or pipes indicate a loss of synchronization, packet portions with their corresponding synchronization codes and states can continue to be read until the synchronization codes indicate that packet portions read from both paths came from the same packet. Then, the portions can be combined into a full data packet, and the packet can be forwarded for further processing. The process of grouping packet portions into full packets is thus realigned or resynchronized, and full packet forwarding resumes.
In one embodiment, the state machines in the individual processing paths or xe2x80x9cpipesxe2x80x9d, referred to herein as xe2x80x9cpipe sync state machinesxe2x80x9d or xe2x80x9cpipe state machinesxe2x80x9d analyze the pattern of synchronization codes for successive portions of data packets being processed in their respective paths to assign an associated state to each portion. The states are then combined with the data packet portion and its synchronization code, and all three items are forwarded together along the path. The synchronization codes can be assigned to portions in a pattern that repeats periodically such that when the grouping device reads the packet portions and associated codes and states, it can determine if the packet portions should be grouped together. In one embodiment, a state machine along one of the paths can detect a discrepancy in the pattern of synchronization codes to identify an error in the data and can in response optionally drop the portion of the data packet. Packet portions can also be dropped within the individual pipes as a result of parity checking.
The grouping processor can also include a state machine which defines a state based on the packet portions read from the storage devices. The grouping processor can also analyze the pattern of synchronization codes associated with successive portions read from the storage devices. Where a discrepancy between code patterns for successive portions is discovered, the grouping processor can determine that an error has occurred and can take steps to ensure that a data packet is not generated by combining the portions that indicate an error. For example, where the states indicate that portions of packets are out of synchronization, the grouping processor can discard data of incoming packet portions as long as the synchronization codes continue to indicate that an error exists. When the synchronization codes are realigned, the grouping processor can resume grouping the portions together in packets and forwarding the packets for further processing. Thus, the system of the invention can detect errors in the forwarding of packet portions and can recover from the error by resynchronizing the data portions with each other.
As mentioned above, the synchronization codes for successive like portions of data packets, i.e., portions of successive data packets stored in the same storage device, are assigned a series of values which repeats periodically. In one particular embodiment, each synchronization code is assigned one of three possible values. By convention, a first value is referred to as a positive, xe2x80x9c+,xe2x80x9d or xe2x80x9cAxe2x80x9d value. The second value is referred to as a negative, xe2x80x9cxe2x88x92,xe2x80x9d or xe2x80x9cBxe2x80x9d value. The third value is referred to as a null or idle value. In one embodiment, the A and B values alternate and they are separated from each other by a predetermined number of idle values. For example, a first packet portion can be assigned an A value and the next succeeding three packet portions can be assigned idle values; the next packet portion can be assigned a B value followed by three more idle values which are followed by the next A value.
The pattern of synchronization codes can repeat as packets continue to be received and split for processing through the individual paths. In one embodiment, as a data packet is received at the splitting device, it is split into multiple, e.g., two, portions, and each portion is associated with the same synchronization code value. At the grouping end, when these packet portions are retrieved from the storage device, they can be grouped back together because they have the same synchronization code value.
When the grouping processor determines that a synchronization code and/or a state associated with a portion of a data packet indicates that an error has occurred in the synchronization code sequence, the grouping device can recover from the loss of synchronization such that correct packet portions can resume being properly grouped together into data packets. For example, if one of the portions is associated with an A synchronization code and another portion is an idle or B code, the grouping processor can read and discard packet portions from the side with the idle or B value until another A value synchronization code packet portion is retrieved from that side. The two A packet portions can be grouped together into a data packet, and normal operation can resume for subsequent packets.
The storage devices can be first-in-first-out (FIFO) storage devices. The packet portions, their associated synchronization codes and associated states can be loaded into the FIFOs at one end by the individual path or pipe processors and removed from the FIFOs at the opposite ends by the grouping processor. Hence, an essentially a synchronous communication between the individual processing paths and the grouping processor is established.
Hence, the present invention provides an efficient means for reassembling data packets that have been split for purposes for parallel processing. The invention exploits the fact that it is acceptable to lose a certain small number of data packets on an occasional basis without seriously impacting the overall performance of the system in which it resides. The system does not require that data that exhibits errors be read again in order to allow for correct regrouping. This makes the system applicable in systems where large amounts of data are being transferred at very fast rates and rereading the data would be impracticable. This feature makes the invention applicable in settings where there is an a synchronous relationship among the individual processing paths and also between the processing paths and the grouping device. Because the grouping device has the ability to recognize and recover from data errors by analyzing only the information stored in the storing devices, the grouping device can operate independently of, and without real-time instructions from, the individual processing paths and without transferring any information back to the individual paths. Therefore the grouping function can be performed independently and efficiently and at a location remote from the individual paths.
The foregoing and other objects, features, and advantages of the invention will be apparent from the following more particular description of preferred embodiments of the invention, as illustrated in the accompanying drawings in which like reference characters refer to the same parts throughout the different views. The drawings are not necessarily to scale, emphasis instead being placed upon illustrating the principles of the invention.
FIG. 1 is a schematic top-level functional block diagram of one embodiment of the apparatus of the invention for transferring data packets from a source device to a destination device by splitting the packets and transferring portions of packets along parallel data paths and then grouping the portion back into their original packets.
FIG. 2 contains a schematic detailed block diagram of one embodiment of the splitting circuitry in the system of FIG. 1.
FIG. 3 contains a schematic detailed block diagram of one embodiment of the grouping circuitry shown in FIG. 1.
FIG. 4 contains a schematic state diagram illustrating the states of a pipe state machine used in one embodiment of the invention.
FIG. 5 contains a schematic flow chart illustrating one embodiment of the logical flow of the grouping function in accordance with the invention.
FIG. 6A is a schematic timing diagram which illustrates operation of the invention where a missed idle synchronization cycle occurs.
FIG. 6B is a schematic timing diagram which illustrates operation of the invention where two missed idle synchronization cycles occur.
FIG. 6C is a schematic timing diagram which illustrates operation of the invention where a missed positive synchronization cycle occurs.
FIG. 6D is a schematic timing diagram which illustrates operation of the invention where a missed negative synchronization cycle occurs.